package com.jacklei.ch12;

import sun.security.provider.MD5;

import java.awt.*;
import java.lang.annotation.ElementType;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/*
* 编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

 

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
 

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

public class LongestCommonPrefix {
    //前缀树
    public static void main(String[] args) {
        LongestCommonPrefix l = new LongestCommonPrefix();
        System.out.println(l.longestCommonPrefix2(new String[]{"flower","flow","flight"}));
        System.out.println(('\0'+"123"));
    }
    public String longestCommonPrefix(String[] strs) {
        Info info = new Info("", 0);
        int N = strs.length;
        for (int i = 0; i < N; i++) {

            Info cur = info;
            cur.count +=1;
            for (int j = 0; j < strs[i].length(); j++) {
                String c = strs[i].substring(j,j+1);
                if("".equals(c)) {
                    break;
                }
                if(cur.child.containsKey(c)){
                    cur.child.get(c).count ++;
                    cur = cur.child.get(c);
                }else if(i == 0) {
                    Info info1 = new Info(c);
                    cur.child.put(c,info1);
                    cur = info1;
                }else break;
            }
        }
        //前缀树
        String res = "";
        while(info != null){
            if(info.count == N){
                res += info.value;
                if(info.child.entrySet().iterator().hasNext()){
                info = info.child.entrySet().iterator().next().getValue();
                }else info = null;
            }else{
                break;
            }
        }

        return res.toString();
    }
    class Info{
        String value;
        int count =1;
        HashMap<String, Info> child = new HashMap<>();

        public Info(String value, int count) {
            this.value = value;
            this.count = count;
        }

        public Info(String value) {
            this.value = value;
        }
    }
    //横向扫描
    public String longestCommonPrefix1(String[] strs){
        int length = strs.length;
        String ans = strs[0];
        for (int i = 0; i < length; i++) {
               ans =  LCP(ans,strs[i]);
               if("".equals(ans))return ans;
        }
        return ans;
    }
    //纵向扫描
    public String longestCommonPrefix2(String[] strs){
        int length = strs.length;
        if(length == 1) return strs[1];
        int length1 = strs[0].length();
        String ans = "";
        for (int j = 0; j < length1; j++) {
            for (int i = 0; i < length-1; i++) {
                if(!(j < strs[i].length()) || !(j < strs[i+1].length()) || strs[i].charAt(j) != strs[i+1].charAt(j)){
                    return ans;
                }
                if(i == length-2){
                    ans += strs[i].charAt(j);
                }
            }

        }

        return ans;
    }
    //分治
    public String longestCommonPrefix3(String[] strs){
        if(strs == null || strs.length == 0 ){
            return "";
        }else {
            return longestCommonPrefix3(strs,0,strs.length-1);
        }
    }

    private String longestCommonPrefix3(String[] strs, int l, int r) {
        if(l == r) return strs[l];
        else {
            int mid = (r - l) / 2 + l;
            String lcpL = longestCommonPrefix3(strs,l,mid);
            String lcpR = longestCommonPrefix3(strs,mid+1,r);
            return commonPrefix3(lcpL,lcpR);
        }


    }

    private String commonPrefix3(String lcpL, String lcpR) {
        int midLength = Math.min(lcpL.length(),lcpR.length());
        for (int i = 0; i < midLength; i++) {
            if(lcpL.charAt(i) != lcpR.charAt(i)){
                return lcpL.substring(0,i);
            }
        }
        return lcpL.substring(0,midLength);
    }
    //二分查找
    public String longestCommonPrefix4(String[] strs){
        if(strs == null || strs.length == 0 )
            return "";
        int midLength = Integer.MAX_VALUE;
        for(String str : strs){
            midLength = Math.min(midLength,str.length());
        }
        int low = 0,high = midLength;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if(isCommonPrefix4(strs,mid)){
                low =mid;
            }else {
                high = mid -1;
            }
        }

        return strs[0].substring(0,low);
    }

    private boolean isCommonPrefix4(String[] strs, int mid) {
        String s0 = strs[0].substring(0, mid);
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            String s1 = strs[i];
            for (int j = 0; j < mid; j++) {
                if(s0.charAt(j) != s1.charAt(j))
                    return false;
            }
        }
        return true;
    }

    public String LCP (String s1, String s2) {
        String ans = "";
        int N = Math.min(s1.length(),s2.length());
        for (int i = 0; i < N; i++) {
            if(s1.charAt(i) == s2.charAt(i))
            {
                ans +=s1.charAt(i);
            }else break;
        }
        return ans;
    }
}
